package controller;

import helper.Helper;

import java.math.BigInteger;


public class Euclide {


	public BigInteger algorihtmeEuclideEtendu(BigInteger a,BigInteger b){

		//initialisation
		BigInteger r0 = a ;
		BigInteger r1 = b ;
		BigInteger u0 = new BigInteger("1") ;
		BigInteger u1 = new BigInteger("0") ;
		BigInteger v0 = new BigInteger("0") ;
		BigInteger v1 = new BigInteger("1") ;

		//variable temporaire
		BigInteger u_tmp,  v_tmp , r_tmp, quotient_tmp ;

		while(!r1.equals(new BigInteger("0"))){

			quotient_tmp = r0.divide(r1) ;
			r_tmp = r0; u_tmp = u0;	v_tmp = v0;
			r0 = r1;
			u0 = u1;
			v0 = v1;
			r1 = r_tmp.subtract(quotient_tmp.multiply(r1));
			u1 = u_tmp.subtract(quotient_tmp.multiply(u1));
			v1 = v_tmp.subtract(quotient_tmp.multiply(v1));
			
	
		}
		return u0 ;
	}
	
	public BigInteger normalize(BigInteger u, BigInteger m)
	{
		BigInteger _2 = new BigInteger("2");
		BigInteger k = new BigInteger("-1");
		BigInteger uMinusKTimesM = u.subtract(k.multiply(m));
		
		while(Helper.isInferior(uMinusKTimesM, _2) && Helper.isSuperior(uMinusKTimesM, m))
		{
			k = k.min(k);
			uMinusKTimesM =  u.subtract(k.multiply(m));
		}
		
		return uMinusKTimesM;
	}
	

}
